# 9/100 滑动窗口-找到字符串中所有字母异位词
# leetcode第438题: https://leetcode.cn/problems/find-all-anagrams-in-a-string/description/?envType=study-plan-v2&envId=top-100-liked
# Date: 2024/11/19
import copy
import json
import time
from leetcode import test


def findAnagrams(s: str, p: str) -> list[int]:
    """一种直观的解法"""
    n, win = len(s), len(p)
    res = []

    for start in range(n - win + 1):
        sub_str = s[start:start + win]  # 窗口截取的子字符串
        cp = copy.deepcopy(p)
        for i in range(win):
            if sub_str[i] not in cp:
                break
            else:
                cp = cp.replace(sub_str[i], '', 1)
        if not cp:
            res.append(start)
        start += 1
    return res


def findAnagrams_bf(s: str, p: str) -> list[int]:
    """优化上面的解法"""
    n, win = len(s), len(p)
    if win > n:
        return []
    res = []
    mapping = {}

    # 统计p中每个字符出现的次数
    for i in range(win):
        if mapping.get(p[i]):
            mapping[p[i]] += 1
        else:
            mapping[p[i]] = 1

    for start in range(n - win + 1):
        sub_str = s[start:start + win]  # 窗口截取的子字符串
        cp = copy.deepcopy(mapping)
        mark = 1
        for i in range(win):
            if not cp.get(sub_str[i]):
                mark = i
                break
            else:
                if cp.get(sub_str[i]) == 0:
                    mark = i
                    break
                else:
                    cp[sub_str[i]] -= 1
        flag = True
        for v in cp.values():
            if v != 0:
                flag = False
                break
        if flag:
            res.append(start)
        start += mark
    return res


def findAnagrams_swin(s: str, p: str) -> list[int]:
    """使用滑动窗口"""
    n, win = len(s), len(p)
    if win > n:
        return []
    res = []
    s_count = [0] * 26
    p_count = [0] * 26
    code_a = ord('a')  # 97

    for i in range(win):
        s_count[ord(s[i]) - code_a] += 1
        p_count[ord(p[i]) - code_a] += 1

    if s_count == p_count:
        res.append(0)

    for i in range(n - win):
        s_count[ord(s[i]) - code_a] -= 1
        s_count[ord(s[i + win]) - code_a] += 1

        if s_count == p_count:
            res.append(i + 1)
    return res


def findAnagrams_swin_opt(s: str, p: str) -> list[int]:
    """进一步优化滑动窗口"""
    n, win = len(s), len(p)
    if win > n:
        return []
    res = []
    cnt = [0] * 26
    code_a = ord('a')  # 97

    for i in range(win):
        cnt[ord(s[i]) - code_a] += 1
        cnt[ord(p[i]) - code_a] -= 1

    differ = [c != 0 for c in cnt].count(True)  # 统计数组中True的数量

    if differ == 0:
        res.append(0)

    for i in range(n - win):
        if cnt[ord(s[i]) - code_a] == 1:  # 窗口中字母 s[i] 的数量与字符串 p 中的数量从不同变得相同
            differ -= 1
        elif cnt[ord(s[i]) - code_a] == 0:  # 窗口中字母 s[i] 的数量与字符串 p 中的数量从相同变得不同
            differ += 1
        cnt[ord(s[i]) - code_a] -= 1

        if cnt[ord(s[i + win]) - code_a] == -1:  # 窗口中字母 s[i+p_len] 的数量与字符串 p 中的数量从不同变得相同
            differ -= 1
        elif cnt[ord(s[i + win]) - code_a] == 0:  # 窗口中字母 s[i+p_len] 的数量与字符串 p 中的数量从相同变得不同
            differ += 1
        cnt[ord(s[i + win]) - code_a] += 1

        if differ == 0:
            res.append(i + 1)

    return res


if __name__ == '__main__':
    with open("../data/c_swin2_lc438.data", "r") as file:
        lines = file.read().strip()  # 去除首位的空白
        jo = json.loads(lines)

    inp = [{"s": "cbaebabacd", "p": "abc"}, {"s": "abab", "p": "ab"}, {"s": "aabbaaba", "p": "aab"},
           {"s": "aa", "p": "bb"}, {"s": jo["s"], "p": jo["p"]}, ]
    out = [[0, 6], [0, 1, 2], [0, 3, 4, 5], [], jo["ans"]]

    test.test_function(findAnagrams, inp, out)  # 18.339668
    test.test_function(findAnagrams_bf, inp, out)  # 15.822651
    test.test_function(findAnagrams_swin, inp, out)  # 0.008006
    test.test_function(findAnagrams_swin_opt, inp, out)  # 0.005964
